//
// Created by liushuai on 2021/1/17.
//

#include "zigzagLevelOrder.h"
std::vector<std::vector<int>> zigzagLevelOrder(TreeNode* root) {
  std::vector<std::vector<int>> result;
  if (!root)
    return result;
  else {
    std::stack<TreeNode*> odd;
    std::stack<TreeNode*> even;
    even.push(root);
    while (!even.empty() || !odd.empty()) {
      int queue_size = even.size();
      std::vector<int> layers;
      for (int i = 0; i < queue_size; i++) {
        TreeNode* current = even.top();
        even.pop();
        layers.push_back(current->val);
        if (current->left) odd.push(current->left);
        if (current->right) odd.push(current->right);
      }
      if (!layers.empty()) {
        result.push_back(layers);
        layers.clear();
      }
      int stack_size = odd.size();
      for (int i = 0; i < stack_size; i++) {
        TreeNode* current = odd.top();
        odd.pop();
        layers.push_back(current->val);
        if (current->right) even.push(current->right);
        if (current->left) even.push(current->left);
      }
      if (!layers.empty()) {
        result.push_back(layers);
        layers.clear();
      }
    }
    return result;
  }
}
